/**
 * Created with IntelliJ IDEA.
 * Description:
 * user:likai
 * Date:2022-10-27
 * Time:11:12
 */
class TreeNode{
    public int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
    public TreeNode(){

    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "val=" + val +
                ", left=" + left +
                ", right=" + right +
                '}';
    }
}
//class Solution{
//    public static int cur=2;
//    public TreeNode buildTree(int[] postorder , int[] inorder) {
//        //根节点
//        TreeNode root= new TreeNode(postorder [inorder.length-1]);
//
//        //找其中的位置
//        int ret=find(inorder,0,inorder.length-1,postorder [inorder.length-1]);
//        root.right=buildTreeChild(postorder ,inorder,ret+1,inorder.length-1);
//        root.left=buildTreeChild(postorder ,inorder,0,ret-1);
//        return root;
//    }
//    public int find(int[] inorder, int begin,int end,int val){
//        for (int i = begin; i <= end; i++) {
//            if(inorder[i]==val){
//                return i;
//            }
//        }
//        return -1;
//    }
//    public TreeNode buildTreeChild(int[] postorder , int[] inorder,int begin,int end){
//        //已经找完了
//        if(begin>end){
//            return null;
//        }
//        //开始找下一个
//        int val=postorder [inorder.length-cur];
//        TreeNode root= new TreeNode(val);
//        if(begin==end){
//            cur++;
//            return root;
//
//        }
//        int ret=find(inorder,begin,end,val);
//        //里面没有
//        if(ret==-1){
//            return null;
//        }
//        cur++;
//        root.right=buildTreeChild(postorder ,inorder,ret+1,inorder.length-1);
//        root.left=buildTreeChild(postorder ,inorder,0,ret-1);
//        return root;
//    }
//}

//从后往前走第一个是右子树
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        TreeNode root = new TreeNode();
        root = buildTreeChild(inorder, postorder, 0, inorder.length - 1);
        return root;
    }

    int cur = 1;

    public int find(int[] inorder, int begin, int end, int val) {
        for (int i = begin; i <= end; i++) {
            if (inorder[i] == val) {
                return i;
            }
        }
        return -1;
    }

    public TreeNode buildTreeChild(int[] inorder, int[] postorder, int begin, int end) {
        if (begin > end) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[postorder.length - cur]);
        int mid = find(inorder, begin, end, root.val);
        if (mid == -1) {
            return null;
        }
        cur++;
        if (begin == end) {
            return root;
        }
        root.right = buildTreeChild(inorder, postorder, mid + 1, end);
        root.left = buildTreeChild(inorder, postorder, begin, mid - 1);
        return root;
    }

    //转化成字符串
    public String tree2str(TreeNode root) {
        StringBuffer str = new StringBuffer();
        //先序遍历
        tree2strChild(root,str);
        return str.toString();
    }

    public void tree2strChild(TreeNode root,StringBuffer str) {
        if(root==null){
            return;
        }
        str.append(root.val);
        if(root.left!=null||root.right!=null){
            str.append('(');
            tree2strChild(root.left,str);
            str.append(')');
        }
        if(root.right!=null) {
            str.append('(');
            tree2strChild(root.right, str);
            str.append(')');
        }
    }

    public TreeNode create(){
        TreeNode treeNode1=new TreeNode(1);
        TreeNode treeNode2=new TreeNode(2);
        TreeNode treeNode3=new TreeNode(3);
        TreeNode treeNode4=new TreeNode(4);
        treeNode1.left=treeNode2;
        treeNode1.right=treeNode3;
        treeNode2.left=treeNode4;
        return treeNode1;
    }
}
public class Test {
    public static void main(String[] args) {
        Solution solution = new Solution();
//        int[] postorder = {9, 15, 7, 20, 3};
//        int[] inorder = {9, 3, 15, 20, 7};
//        TreeNode root = solution.buildTree(postorder, inorder);
//        System.out.println(root);
//        //String str=new String("a");
        TreeNode root=solution.create();
        String string=solution.tree2str(root);
        System.out.println(string);
    }
}
